public class Solution974 {
    public int subarraysDivByK(int[] nums, int k) {
        int[] f=new int[k];
        int last=0;
        for (int i=0;i<nums.length;i++){
            last+=nums[i];
            f[(last%k+k)%k]++;
        }
        int ans=0;
        for (int i = 0; i < k; i++) {
            ans+=(f[i]-1)*f[i]/2;
        }
        return ans+f[0];
    }

    public static void main(String[] args) {
        System.out.println(new Solution974().subarraysDivByK(new int[]{4,5,0,-2,-3,1},5));
    }
}
